package org.aplombh.java.awcing.basic.struct.link;

import java.util.Arrays;

public class MyDoublyLinkList {
    //e[0] = head;
    //e[1] = tail;

    private static final int N = 100010;
    private int index;
    private int[] e;
    private int[] l;
    private int[] r;

    public MyDoublyLinkList() {
        init();
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for(int i = r[0]; i != 1; i = r[i]) builder.append(e[i]).append(" ");
        builder.append("\n");
        return builder.toString();
    }

    void init() {

        // 0 存储右节点
        // 1 存储左节点
        index = 2;
        if (e == null)
            e = new int[N];
        if (l == null)
            l = new int[N];
        if (r == null)
            r = new int[N];

        Arrays.fill(e, 0);
        Arrays.fill(l, 0);
        Arrays.fill(r, 0);

        // 如果为r为1，代表遍历结束
        r[0] = 1;
        l[1] = 0;

    }

    public void add(int k, int x) {
        e[index] = x;

        // 该点右指针指向第k个节点的右边
        r[index] = r[k];
        // 该点的左节点指向k节点
        l[index] = k;

        // 将第k个节点的右节点的左指针指向该节点
        l[r[k]] = index;
        // 将第k个节点的右节点指向该节点
        r[k] = index++;
    }

    public void remove(int k) {
        l[r[k]] = l[k];
        r[l[k]] = r[k];
    }

    public int left(int i) {
        return l[i];
    }


}
